#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <utility>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <inttypes.h>

using namespace std;

#define TAM 512
#define INF 0x3f3f3f3f

int dl[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};

int n,m,k,ans;
int foi[TAM][TAM],vet[TAM];
typedef struct
{
    int l,c;
} TFila;
vector<string> mapa;

void solve(int i,int leva1,int leva2,int a1,int a2)
{

    if (i == k)
    {
        leva1-=a1;
        leva2-=a2;
        ans = min(ans,max(leva1,leva2));
        return;
    }
    solve(i+1,leva1+2*vet[i],leva2,vet[i],a2);
    solve(i+1,leva1,leva2+2*vet[i],a1,vet[i]);
    return;
}

int calcdist(int li,int ci, int lf, int cf)
{
    if (mapa[li][ci] == '$' || mapa[lf][cf] == '$') return 2;
    if (mapa[li][ci] == mapa[lf][cf]) return 1;

    if (max(mapa[lf][cf],mapa[li][ci]) - min(mapa[lf][cf],mapa[li][ci]) == 1) return 3;
    return INF;
}

int valido(int li,int ci, int lf, int cf)
{
    if (lf <0 || lf >=n) return 0;
    if (cf <0 || cf >=m) return 0;
    int dist = calcdist(li,ci,lf,cf);
    if (foi[lf][cf] > foi[li][ci] + dist)
    {
        foi[lf][cf] = foi[li][ci] + dist;
        return 1;
    }
    else return 0;
}

class PizzaDelivery
{

public:
    int deliverAll(vector <string> _mapa)
    {
        mapa = _mapa;
        n = mapa.size();
        m = mapa[0].size();

        int inil=-1,inic=-1;

        for (int i = 0;i<n;i++)
            for (int j = 0;j<m;j++)
            {
                foi[i][j] = INF;
                if (mapa[i][j] == 'X')
                {
                    inil = i;
                    inic = j;
                    mapa[i][j] = '$';
                }
            }
        TFila Fila[TAM*TAM];
        Fila[0].l = inil;
        Fila[0].c = inic;
        foi[inil][inic] = 0;
        int ini = 0,fim = 1;

        while (ini < fim)
        {
            int l = Fila[ini].l;
            int c = Fila[ini].c;
            for (int i=0;i<4;i++)
            {
                if (valido(l,c,l+dl[i],c+dc[i]))
                {
                    Fila[fim].l = l + dl[i];
                    Fila[fim].c = c + dc[i];
                    fim++;
                }
            }
            ini++;
        }

        mapa[inil][inic] = 'X';
        k = 0;
        ans = INF;
        for (int i = 0;i<n;i++)
            for (int j = 0;j<m;j++)
                if (mapa[i][j] == '$')
                {
                    vet[k++] = foi[i][j];
                    if (foi[i][j] == INF) ans = -1;
                }
        sort(vet,vet+k);
        if (ans == -1) return -1;
        else solve(0,0,0,0,0);

        return ans;
    }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
